package utils;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * 实现一个缓存key-value结构，并设定容量最大值，
 * 当put进去的时候，如果超过最大容量，则将最早放进去的删除
 * 当get的时候，返回key值，并将key放到后面（表示最近使用过，最后删除）
 */
public class LRUCache {
        private Map<String, Object> cache;
	    private Deque<String> deque;
	    private int capacity;

        public LRUCache(int capacity) {
	        this.capacity = capacity;
	        this.cache = new HashMap<>();
	        this.deque = new LinkedList<>();
	    }

        public Object get(String key) {
	        if (!cache.containsKey(key)) {
	            return -1;
	        }
	        deque.remove(key); // 删掉原key，将其移到队列尾
	        deque.offerLast(key);
	        return cache.get(key);
	    }

        public void put(String key, Object value) {
	        if (cache.containsKey(key)) {
	            deque.remove(key); // 删掉原key，将其移到队列尾
	        } else if (cache.size() >= capacity) {
	            String removed = deque.pollFirst(); // 移除队首（最久未使用）
	            cache.remove(removed);
	        }
	        cache.put(key, value);
	        deque.offerLast(key);
	    }

    @Override
    public String toString() {
        return "LRUCache{" +
                "cache=" + cache +
                ", deque=" + deque +
                ", capacity=" + capacity +
                '}';
    }
}
